﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

namespace DBMS.Indexes.Tree.BPlus
{
    public abstract class Node<IT>
    {
        private Node<IT>[] parents;
        private ComparableIndex<IT>[] keys;
        private Object[] pointers;
        protected int order;
        protected int nItems;

        public Object InfinityPointer
        {
            get;
            set;
        }
        public int NrItems
        {
            get
            {
                return nItems;
            }
        }

        public Node(int order)
        {
            this.order = order;
            keys = new ComparableIndex<IT>[this.order];
            pointers = new Object[this.order];
            parents = new Node<IT>[this.order];
            nItems = 0;
        }


        public ComparableIndex<IT> GetKey(int i)
        {
            return keys[i];
        }


        public bool IsFull()
        {
            return NrItems >= order;
        }

        public int AddKey(ComparableIndex<IT> key, Object pointer)
        {
            if (IsFull())
            {
                throw new Exception("The Node " + this + " is Full");
            }
            int newIndex = 0;
            // Searching the place of the new index
            for (int i = 0; i < NrItems; i++)
            {
                if (key.lessThanOrEqual(keys[i]))
                {
                    newIndex = i;
                    break;
                }
                else
                {
                    newIndex++;
                }
            }

            if (newIndex < NrItems)
            {
                //Moving one place to right elements in the right
                ComparableIndex<IT> tempFrom, tempTo;
                tempFrom = keys[newIndex];
                for (int i = newIndex + 1; i <= NrItems; i++)
                {
                    tempTo = keys[i];
                    keys[i] = tempFrom;
                    tempFrom = tempTo;
                }


                //Moving one place to right elements in the right
                Object pointerFrom, pointerTo;
                pointerFrom = pointers[newIndex];
                for (int i = newIndex + 1; i <= NrItems - 1; i++)
                {
                    pointerTo = pointers[i];
                    pointers[i] = pointerFrom;
                    pointerFrom = pointerTo;
                }
            }
        

            keys[newIndex] = key;
            pointers[newIndex] = pointer;
            nItems++;
            return newIndex;
        }

        public Object GetPointer(int i)
        {
            return pointers[i];
        }

        public Node<IT> Split(ComparableIndex<IT> key, Object pointer)
        {
            ComparableIndex<IT>[] temp = new ComparableIndex<IT>[order + 1];
            Object[] tempPointers = new Object[order + 1];
            int index = 0;
            bool placed = false;
            for (int i = 0; i < order; i++)
            {
                if (key.lessThan(keys[i]) && (!placed))
                {
                    temp[index] = key;
                    tempPointers[index] = pointer;
                    placed = true;
                    index++;
                }
                temp[index] = keys[i];
                tempPointers[index] = pointers[i];
                index++;
            }

            if (!placed)
            {
                temp[index] = key;
                tempPointers[index] = pointer;
                placed = true;
            }

            int splitIndex = (order + 1) / 2;
            Node<IT> newNode = this.CloneNew();

            for (int i = 0; i < splitIndex; i++)
            {
                newNode.AddKey(temp[i], tempPointers[i]);
            }
            this.Erase();

            for (int i = splitIndex; i < temp.Length; i++)
            {
                AddKey(temp[i], tempPointers[i]);
            }

            return newNode;
        }


        protected void Erase()
        {
            keys = new ComparableIndex<IT>[order];
            pointers = new Object[order];
            nItems = 0;
        }

        protected abstract Node<IT> CloneNew();
    }
}